﻿#define _CRT_SECURE_NO_WARNINGS 1
///**现在有n个人站成一列，第i个人的身高为a_{i-1}a 
//i−1
//​	
// 。
//他们人手一把玩具枪，并且他们喜欢把枪举在头顶上。
//每一次练习射击，他们都会朝正前方发射一发水弹。
//这个时候，第i个人射击的水弹，就会击中在他前面第一个比他高的人。
//牛牛认为这样的练习十分的荒唐，完全就是对长得高的人的伤害。
//于是它定义了一个荒唐度，初始为0。
//对于第i个人，如中他击中了第j个人，则荒唐度加j，如果没有击中任何人，则荒唐度加0.
//牛牛想问你，你能计算出荒唐度是多少吗？
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//*
//* @param n int整型 n个人
//* @param a int整型一维数组 ai代表第i个人的高度
//* @param aLen int a数组长度
//* @return long长整型
//*/
//long long solve(int n, int* a, int aLen) {
//	// write code here
//	long long count = 0, i, j;
//	for (i = n - 1; i >= 1; i--)
//	{
//		for (j = i - 1; j >= 0; j--)
//		{
//			if (a[i] - a[j]<0)
//			{
//				count += j + 1;
//				break;
//			}
//		}
//	}
//	return count;
//}







///**给你一个长度为n的数组A。
//A[i]表示从i这个位置开始最多能往后跳多少格。
//求从1开始最少需要跳几次就能到达第n个格子。
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//* 最少需要跳跃几次能跳到末尾
//* @param n int整型 数组A的长度
//* @param A int整型一维数组 数组A
//* @param ALen int A数组长度
//* @return int整型
//*/
//int Jump(int n, int* A, int ALen) {
//	// write code here
//	int i = 0;
//	int max = 0;
//	for (i = 0; i<n; i++)
//	{
//		if (A[i]>max)
//		{
//			max = A[i];
//		}
//	}
//	n--;
//	if (n%max != 0)
//	{
//		return n / max + 1;
//	}
//	return n / max;
//}
//
//
//
//
//
//
//
///**长度为n的数组，每次可以选择若干元素使元素的值变为这些元素的和的平均值
//给出数组和数字x，求经过操作数组中最多有多少数字不小于x
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//* 最多有多少数字不小于x
//* @param n int整型
//* @param x int整型
//* @param a int整型一维数组
//* @param aLen int a数组长度
//* @return int整型
//*/
//int arrange(int n, int x, int* a, int aLen) {
//	// write code here
//	int i = 0;
//	int count = a[i] - x;
//	while (count >= 0 && i<aLen)
//	{
//		i++;
//		count += a[i] - x;
//	}
//	return i;
//}











///**现在给定一个数组arr，和a,b两个数字，你要做的就是找到（i，j，k）。且满足
//1. 0 <= i < j < k < arr.size()
//2. |arr[i] - arr[j]| <= a
//3. |arr[j] - arr[k]| <= b
//统计满足条件的个数并返回(最后结果可能很大，请取1000000007的余数)。
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//* @param arr int整型一维数组
//* @param arrLen int arr数组长度
//* @param a int整型
//* @param b int整型
//* @return int整型
//*/
//int countTriplets(int* arr, int arrLen, int a, int b) {
//	// write code here
//	int i, j, k;
//	int count1, count2;
//	int num = 0;
//	if (a >= 0 && b >= 0)
//	{
//		for (j = 1; j<arrLen; j++)
//		{
//			count1 = 0;
//			count2 = 0;
//			for (i = 0; i<j; i++)
//			{
//				if (abs(arr[i] - arr[j]) <= a)
//				{
//					count1++;
//				}
//			}
//			for (k = j + 1; k<arrLen; k++)
//			{
//				if (abs(arr[j] - arr[k]) <= b)
//				{
//					count2++;
//				}
//			}
//			num = (num + count1*count2) % 1000000007;
//		}
//	}
//	return num;
//}








//自助餐厅里有5个盘子，里面装的都是面包。
//第1个盘子里有无限个面包；
//第2个盘子里只有1个面包；
//第3个盘子里只有4个面包；
//第4个盘子里也有无限个面包，但必须两个两个地拿；
//第5个盘子里也有无限个面包，但必须5个5个地拿；
//给定正整数n，求有多少种正好拿出n个面包的方案。
//方案a和方案b不同，当且仅当方案a存在从某个盘子里拿出面包的数量与方案b中对应盘子拿出的数量不同
///**
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//* @param n int整型
//* @return long长整型
//*/
//long long wwork(int n) {
//	// write code here
//	long long count = 1;
//	int i = 0;
//	for (i = 1; i <= n; i++)
//	{
//		count += i + 1;
//	}
//	return count;
//}







///**牛牛有一个数组array，牛牛可以每次选择一个连续的区间，
//让区间的数都加1，他想知道把这个数组变为严格单调递增，最少需要操作多少次？
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//*
//* @param array int整型一维数组 array
//* @param arrayLen int array数组长度
//* @return long长整型
//*/
//long long IncreasingArray(int* array, int arrayLen) {
//	// write code here
//	long long i, j;
//	long long count = 0;
//	for (i = 0; i<arrayLen - 1; i++)
//	{
//		if (array[i] >= array[i + 1])
//		{
//			count += array[i] - array[i + 1] + 1;
//		}
//	}
//	return count;
//}
//
//
//
//
//
//
//
///**众所周知，牛妹非常喜欢吃蛋糕。
//第一天牛妹吃掉蛋糕总数三分之一（向下取整）多一个，
//第二天又将剩下的蛋糕吃掉三分之一（向下取整）多一个，
//以后每天吃掉前一天剩下的三分之一（向下取整）多一个，到第n天准备吃的时候只剩下一个蛋糕。
//牛妹想知道第一天开始吃的时候蛋糕一共有多少呢？
//* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//*
//*
//* @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
//* @return int整型
//*/
//int cakeNumber(int n) {
//	// write code here
//	int count = 1;
//	int i = 0;
//	for (i = n - 1; i>0; i--)
//	{
//		count = 3 * (count + 1) / 2;
//	}
//	return count;
//}









//在不使用额外的内存空间的条件下判断一个整数是否是回文数字
//提示：
//负整数可以是回文吗？（比如 - 1）
//如果你在考虑将数字转化为字符串的话，请注意一下不能使用额外空间的限制
//你可以将整数翻转。但是，如果你做过题目“反转数字”，你会知道将整数翻转可能会出现溢出的情况，你怎么处理这个问题？
//class Solution {
//public:
//	/**
//	*
//	* @param x int整型
//	* @return bool布尔型
//	*/
//	bool isPalindrome(int x) {
//		// write code here
//		if (x<0 || x != 0 && x % 10 == 0)
//		{
//			return false;
//		}
//		int count = 0;
//		while (x>count)
//		{
//			count = count * 10 + x % 10;
//			x /= 10;
//		}
//		return (count == x || count / 10 == x);
//	}
//};